package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/clone-graph/description/'>克隆图(Clone Graph)</a>
 * <p>给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。</p>
 * <p>
 * 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
 * <pre>
 * class Node {
 *     public int val;
 *     public List<Node> neighbors;
 * }
 * </pre>
 * </p>
 * <p>给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/clone-graph/description/'>查看原题</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>节点数不超过 100 。</li>
 *         <li>每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。</li>
 *         <li>无向图是一个简单图，这意味着图中没有重复的边，也没有自环。</li>
 *         <li>由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。</li>
 *         <li>图是连通图，你可以从给定节点访问到所有节点。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/26 14:56
 */
public class LC0133CloneGraph_M {

    static class Solution {
        public Node cloneGraph(Node node) {
            if (node == null) {
                return null;
            }
            Map<Node, Node> visited = new HashMap<>();
            Queue<Node> queue = new LinkedList<>();
            queue.offer(node);
            visited.put(node, new Node(node.val));
            while (!queue.isEmpty()) {
                Node currNode = queue.poll();
                for (Node neighbor : currNode.neighbors) {
                    if (!visited.containsKey(neighbor)) {
                        queue.offer(neighbor);
                        visited.put(neighbor, new Node(neighbor.val));
                    }
                    // 更新当前节点的邻居列表
                    visited.get(currNode).neighbors.add(visited.get(neighbor));
                }
            }
            return visited.get(node);
        }
    }

    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.neighbors.add(node2);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node1);
        node3.neighbors.add(node4);
        node4.neighbors.add(node2);
        node4.neighbors.add(node3);
        Solution solution = new Solution();
        Node node = solution.cloneGraph(node1);
    }
}
